<?php
// +----------------------------------------------------------------------
// | 算法二：动态规划(Dynamic programming)
// | 基本思想：
// |   将待求解问题分解成若干个子问题，先解决子问题，然后从这些子问题待解得到愿问题的解
// | 步骤：
// |  （1）分析最优解的性质，并刻画其结构特征。
// |  （2）递归的定义最优解。
// |  （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
// |  （4）根据计算优值时得到的信息，构造问题的最优解。
// | 典型实例：
// |   1）0-1背包问题
// |   2）最长公共子序列 (LCS)
// |   3）找零钱问题
// |   4）走方格问题
// |   5）走台阶问题
// +----------------------------------------------------------------------

namespace helper\algorithm;

class DynamicProgramming
{
    public function demo()
    {
        $n      = 5;
        $w      = 17;
        $weight = [4, 5, 10, 11, 13];
        $value  = [3, 4, 7, 8, 9];
        $array = $this->knapsackDP($n, $w, $value, $weight);
        var_dump($array);
        $this->outputKnapsackDP($n, $w, $value, $weight, $array);

        $str1 = 'ABCBDAB';
        $str2 = 'BDCABA';
        $str1_length = strlen($str1);
        $str2_length = strlen($str2);

        $b = $this->lcsLength($str1, $str2, $str1_length, $str2_length);
        var_dump($b);
        $this->outputLcs($str1, $b, $str1_length, $str2_length);
    }

    /**
     * 0-1背包问题
     * 一个承受最大重量为W的背包，现在有n个物品，每个物品重量为t, 每个物品的价值为v。
     * 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大
     *
     * 计算背包问题最优解的值
     * 时间复杂度：O(nW)
     * @param int $n 物品数量
     * @param int $w 背包容量
     * @param array $value 物品价值
     * @param array $weight 物品重量
     * @return array
     */
    public function knapsackDP(int $n, int $w, array $value, array $weight): array
    {
        // 为二维数组申请空间
        $c = [];
        for ($i = 0; $i <= $n; $i++) {
            $c[$i] = [];
        }

        // 初始化二维数组 情况1：c[i,w]=0,i=0或w=0
        for ($j = 0; $j <= $w; $j++) {
            $c[0][$j] = 0;
        }
        for ($i = 1; $i <= $n; $i++) {
            $c[$i][0] = 0;
            for ($j = 1; $j <= $w; $j++) {
                // 如果背包剩余重量大于物品重量
                if ($weight[$i - 1] <= $j) {
                    // 情况2：max{c[i-1,w-wi] + vi,c[i-1,w]},i>0且wi<=w
                    if ($value[$i - 1] + $c[$i - 1][$j - $weight[$i - 1]] > $c[$i - 1][$j]) {
                        // 重量为w的背包中放入该物品
                        $c[$i][$j] = $value[$i - 1] + $c[$i - 1][$j - $weight[$i - 1]];
                    } else {
                        // 重量为w的背包中不放入该物品
                        $c[$i][$j] = $c[$i - 1][$j];
                    }
                } else {
                    // 情况3：c[i-1,w],wi>w
                    $c[$i][$j] = $c[$i - 1][$j];
                }
            }
        }
        return $c;
    }

    /**
     * 0-1背包问题
     * 根据计算的结果构造问题最优解
     * 时间复杂度：O(n)
     * @param int $n 物品数量
     * @param int $w 背包容量
     * @param array $value 物品价值
     * @param array $weight 物品重量
     * @param array $c
     * @return void
     */
    public function outputKnapsackDP(int $n, int $w, array $value, array $weight, array $c): array
    {
        $x = [];
        for ($i = $n; $i > 1; $i--) {
            // 重量为w的最优选择的背包中不包含该物品
            if ($c[$i][$w] == $c[$i - 1][$w]) {
                $x[$i - 1] = 0;
            } else {
                $x[$i - 1] = 1;
                $w         = $w - $weight[$i - 1];//更新背包目前的最大容量
            }
        }

        if ($c[1][$w] == 0) {
            $x[0] = 0;//第一个物品不放入背包
        } else {
            $x[0] = 1;//第一个物品放入背包
        }
        for ($i = 0; $i < $n; $i++) {
            if ($x[$i] == 1)
                printf("Weight:$weight[$i],Value:$value[$i]");
        }
    }

    /**
     * 最长公共子序列 (LCS)
     * 从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到
     * 应用：程序代码相似度度量，检查论文的抄袭率
     * 1）子序列(subsequence)： 一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。
     *  例如序列A,B,C,B,D,A,B的子序列有：A,B、B,C,A、A,B,C,D,A等
     * 2）公共子序列(common subsequence)： 给定序列X和Y，序列Z是X的子序列，也是Y的子序列，则Z是X和Y的公共子序列。
     *  例如X=[A,B,C,B,D,A,B]，Y=[B,D,C,A,B,A[，那么序列Z=[B,C,A]为X和Y的公共子序列，其长度为3。
     * 但Z不是X和Y的最长公共子序列，而序列[B,C,B,A]和[B,D,A,B]也均为X和Y的最长公共子序列，长度为4，而X和Y不存在长度大于等于5的公共子序列。
     * 对于序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[]。
     * 3）最长公共子序列：给定序列X和Y，从它们的所有公共子序列中选出长度最长的那一个或几个。
     * 4）子串： 将一个序列从最前或最后或同时删掉零个或几个字符构成的新系列。区别与子序列，子序列是可以从中间抠掉字符的。
     * cnblogs这个字符串中子序列有多少个呢？很显然有27个，比如其中的cb,cgs等等都是其子序列
     * 子序列不一定是连续的，连续的是子串。
     * 时间复杂度：O(mn)
     * @param string $str1 序列X
     * @param string $str2 序列Y
     * @param int $str1_length 序列X的长度
     * @param int $str2_length 序列Y的长度
     * @return array
     */
    public function lcsLength(string $str1, string $str2, int $str1_length, int $str2_length): array
    {
        // 为矩阵l，b分配空间
        $l = [];// 长度矩阵
        $b = [];// 方向矩阵
        for ($i = 0; $i <= $str1_length; $i++) {
            $l[$i] = [];
            $b[$i] = [];
        }
        // 初始化矩阵 情况1：l[i,j] = 0,i=0或j=0
        for ($i = 1; $i <= $str1_length; $i++) {
            $l[$i][0] = 0;
        }
        for ($i = 0; $i <= $str2_length; $i++) {
            $l[0][$i] = 0;
        }
        for ($i = 1; $i <= $str1_length; $i++) {
            for ($j = 1; $j <= $str2_length; $j++) {
                // 情况2：l[i-1,j-1] + 1,i，j>0且xi=yj
                if ($str1[$i - 1] == $str2[$j - 1]) {
                    $l[$i][$j] = $l[$i - 1][$j - 1] + 1;
                    $b[$i][$j] = 0;// 1代表指向左上方箭头
                // 情况3：max{l[i-1,j]，l[i,j-1]},i，j>0且xi!=yj
                } else if ($l[$i - 1][$j] >= $l[$i][$j - 1]) {
                    $l[$i][$j] = $l[$i - 1][$j];
                    $b[$i][$j] = 1;// 1代表指向上方箭头
                } else {
                    $l[$i][$j] = $l[$i][$j - 1];
                    $b[$i][$j] = 2;// 2代表指向左方箭头
                }
            }
        }
        return $b;
    }

    /**
     * 最长公共子序列[2021年11月]
     * O(m8n)
     */
    public function distance(string $str1,int $len1, string $str2, int $len2)
    {
        $d = [];
        for($i=0;$i<=$len1;$i++){
            $d[$i][0]=$i;
        }
        for($j=0;$j<=$len2;$j++){
            $d[0][$j]=$j;
        }
        for($i=1;$i<=$len1;$i++){
            for($j=1;$j<=$len2;$j++){
                if ($str1[$i-1]==$str2[$j-1]) {
                    $d[$i][$j] = $d[$i-1][$j-1];
                } else {
                    $temp = min($d[$i-1][$j]+1, $d[$i][$j-1]+1);
                    $d[$i][$j] = min($temp, $d[$i-1][$j-1]+1);
                }
            }
        }
        return $d[$len1][$len2];
    }

    /**
     * 构造最优解
     * @param string $str1 序列X
     * @param array $b 方向矩阵
     * @param int $str1_length 序列X的长度
     * @param int $str2_length 序列Y的长度
     * @return void
     */
    public function outputLcs(string $str1, array $b, int $str1_length, int $str2_length)
    {
        if ($str1_length == 0 || $str2_length == 0) {
            return;
        }
        if ($b[$str1_length][$str2_length] == 0) {
            $this->outputLcs($str1, $b, $str1_length - 1, $str2_length - 1);
            echo $str1[$str1_length - 1];
        } else if ($b[$str1_length][$str2_length] == 1) {
            $this->outputLcs($str1, $b, $str1_length - 1, $str2_length);
        } else {
            $this->outputLcs($str1, $b, $str1_length, $str2_length - 1);
        }
    }
}